package graph

import "fmt"

func DFS(graph map[string][]string, startVertex string, op func(string)) {
	visited := make(map[string]bool)
	var queue []string

	vertexes := graph[startVertex]
	visited[startVertex] = true
	queue = append(queue, vertexes...)

	for {
		if len(queue) == 0 {
			break
		}
		e := queue[len(queue)-1]
		queue = queue[:len(queue)-1]
		if !visited[e] {
			op(e)
		}
		visited[e] = true
		vs := graph[e]
		for _, v1 := range vs {
			if visited[v1] {
				continue
			}
			queue = append(queue, v1)
		}
	}
}

func DFSv2(graph map[string][]string, s string) {
	var stack []string

	// 这里可以替换成一个集合，由于go语言默认有没有set类型， 所以这里使用map替代
	visited := make(map[string]bool)

	stack = append(stack, s)
	visited[s] = true
	for {
		if len(stack) <= 0 {
			break
		}

		// pop
		vertex := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		neighbors := graph[vertex]
		for _, n := range neighbors {
			if !visited[n] {
				stack = append(stack, n)
				visited[n] = true
			}
		}
		fmt.Println(vertex)
	}
}
